<?php

class Graph {
	protected $matrix = array();
	protected $vertices = array();

	public function __construct($numberOfVertices) {
		for ($i = 1; $i <= $numberOfVertices; $i++) {
			$vertex = new Vertex($i);
			$this->addVertex($vertex);
		}

		$this->generateMatrix();

		$this->createNeighbourhoods();
	}
	
	public function save() {
		DB::insert('graph', array('matrix' => serialize($this->matrix), 'number_of_vertices' => count($this->vertices), 'graph_type' => $this->type));
	}
	
	protected function generateMatrix() {
		for ($i = 1; $i <= count($this->vertices); $i++) {
			for ($j = $i; $j <= count($this->vertices); $j++) {
				if ($i == $j) {
					$edge = 0;
				} else {
					$edge = rand(0, 1);
				}

				if ($edge) {
					$this->matrix[$i][$j] = $edge;
					$this->matrix[$j][$i] = $edge;
				}
			}
		}
	}
	
	protected function createNeighbourhoods() {
		foreach ($this->vertices as $vertex1) {
			foreach ($this->vertices as $vertex2) {
				if (isset($this->matrix[$vertex1->getId()][$vertex2->getId()])) {
					if ($this->matrix[$vertex1->getId()][$vertex2->getId()]) {
						$vertex1->addNeighbour($vertex2);
					}
				}
			}
		}
	}
	
	public function addVertex(Vertex $vertex) {
		if (!in_array($vertex, $this->vertices)) {
			$this->vertices[$vertex->getId()] = $vertex;
		}
	}
	
	public function getMatrix() {
		return $this->matrix;
	}

	public function getVertices() {
		return $this->vertices;
	}
	
	public function getVerticesCount() {
		return count($this->getVertices());
	}
	
	public function getMinimalDegreeVertex($vertices = null) {
		$minimal = null;

		if ($vertices === null)
			$vertices = $this->getVertices();

		foreach ($vertices as $vertex) {
			if ($minimal !== null) {
				if ($minimal->getDegree() > $vertex->getDegree()) {
					$minimal = $vertex;
				}
			} else {
				$minimal = $vertex;
			}
		}

		return $minimal;
	}
	
	public function getRandomMaximalDegreeVertex($vertices = null) {
		
		$maximalVertices = array();
		if ($vertices === null) {
			$vertices = $this->getVertices();
		}
		$maximal = $this->getMaximalDegreeVertex($vertices);

		foreach ($vertices as $vertex) {
			if ($maximal->getDegree() == $vertex->getDegree()) {
				$maximalVertices[] = $vertex;
			}
		}

		return $maximalVertices[rand(0, count($maximalVertices) - 1)];
	}
	
	public function getMaximalDegreeVertex($vertices = null) {
		$maximal = null;

		if ($vertices === null) {
			$vertices = $this->getVertices();
		}

		foreach ($vertices as $vertex) {
			if ($maximal !== null) {
				if ($maximal->getDegree() < $vertex->getDegree()) {
					$maximal = $vertex;
				}
			} else {
				$maximal = $vertex;
			}
		}

		return $maximal;
	}
	
	public function getVerticesWithMaximumColoredNeighbours($vertices = null) {
		$maximal = array();

		if ($vertices === null) {
			$vertices = $this->getVertices();
		}

		$maximum = $this->getMaximumColoredNeighbours($vertices);

		foreach ($vertices as $vertex) {
			if ($vertex->getColor() == 0 && $vertex->getColoredNeighbours() == $maximum) {
				$maximal[] = $vertex;
			}
		}
		return $maximal;
	}
	
	public function getMaximumColoredNeighbours($vertices = null) {
		$maximum = 0;
		if ($vertices === null) {
			$vertices = $this->getVertices();
		}

		foreach ($vertices as $vertex) {
			if ($vertex->getColor() == 0 && $vertex->getColoredNeighbours() > $maximum) {
				$maximum = $vertex->getColoredNeighbours();
			}
		}
		return $maximum;
	}
	
	public function getMaximalColor($vertices = null) {
		$maximal = 0;
		if ($vertices === null) {
			$vertices = $this->getVertices();
		}

		foreach ($vertices as $vertex) {
			if ($vertex->getColor() > $maximal) {
				$maximal = $vertex->getColor();
			}
		}
		return $maximal;
	}
	
	public function getMinimalColor($vertices = null) {
		if ($vertices === null) {
			$vertices = $this->getVertices();
		}
		$minimal = count($vertices);
			
		foreach ($vertices as $vertex) {
			if ($vertex->getColor() < $minimal) {
				$minimal = $vertex->getColor();
			}
		}
		return $minimal;
	}
	
	public function getMinimalFreeColor($vertices = null) {
		if ($vertices === null) {
			$vertices = $this->getVertices();
		}

		$colors = $this->getColors();

		foreach ($vertices as $vertex) {
			if (in_array($vertex->getColor(), $colors)) {
				$key = array_search($vertex->getColor(), $colors);
				if ($key !== false) {
					unset($colors[$key]);
				}
			}
		}

		return min($colors);
	}
	
	public function getColors() {
		$colors = array();
		for ($i = 1; $i <= count($this->getVertices()); $i++) {
			$colors[] = $i;
		}
		return $colors;
	}
	
	public function check() {
		$vertices = $this->getVertices();

		foreach ($vertices as $vertex) {
			if ($vertex->getColor() == 0) {
				return false;
			}
		
			foreach ($this->getVertexNeighbours($vertex) as $neighbour) {
				if ($vertex->getId() != $neighbour->getId() && $vertex->getColor() == $neighbour->getColor()) {
					return false;
				}
			}
		}
		return true;
	}
	
	public function getVertexNeighbours(Vertex $vertex) {
		$neighbours = array();
		foreach ($vertex->getNeighbours() as $neighbourId) {
			$neighbours[] = $this->vertices[$neighbourId];
		}
		return $neighbours;
	}
	
	public function setVertexColor(Vertex $vertex, $color) {
		if ($vertex->getColor() == 0 && $color != 0) {
			foreach ($this->getVertexNeighbours($vertex) as $neighbour) {
				$neighbour->addColoredNeighbour();
			}
		} elseif ($vertex->getColor() != 0 && $color == 0) {
			foreach ($this->getVertexNeighbours($vertex) as $neighbour) {
				$neighbour->removeColoredNeighbour();
			}
		}
		
		$vertex->setColor($color);
	}
	
	public function getNonColoredVertices($vertices = null) {
		if ($vertices === null) {
			$vertices = $this->getVertices();
		}

		$returnedVertices = array();
		foreach ($vertices as $vertex) {
			if ($vertex->getColor() == 0) {
				$returnedVertices[] = $vertex;
			}
		}
		return $returnedVertices;
	}
	
	public function getColorsCount() {
		$colors = array();
		foreach ($this->vertices as $vertex) {
			if ($vertex->getColor() != 0) {
				if (!in_array($vertex->getColor(), $colors)) {
					$colors[] = $vertex->getColor();
				}
			} else {
				throw new Exception('Non colored vertex id=' . $vertex->getId());
			}
		}
		return count($colors);
	}
	
	protected function getMaximumConflicts() {
		$conflicts = 0;
		foreach ($this->getMatrix() as $row) {
			foreach ($row as $value) {
				if ($value == 1) {
					$conflicts++;
				}
			}
		}
		$conflicts = $conflicts / 2;
		return $conflicts;
	}

	protected function getRealConflicts() {
		$conflicts = 0;
		foreach ($this->getVertices() as $vertex) {
			foreach ($this->getVertexNeighbours($vertex) as $neighbour) {
				if ($vertex->getId() != $neighbour->getId() && $vertex->getColor() == $neighbour->getColor()) {
					$conflicts++;
				}
			}
		}
		$conflicts = $conflicts / 2;
		return $conflicts;
	}
	
	public function getConflictedVertices() {
		$conflictedVertices = array();
		foreach ($this->getVertices() as $vertex) {
			foreach ($this->getVertexNeighbours($vertex) as $neighbour) {
				if ($vertex->getId() != $neighbour->getId() && $vertex->getColor() == $neighbour->getColor()) {
					if (!in_array($vertex, $conflictedVertices)) {
						$conflictedVertices[] = $vertex;
					}
					if (!in_array($neighbour, $conflictedVertices)) {
						$conflictedVertices[] = $neighbour;
					}
				}
			}
		}
		return $conflictedVertices;
	}
	
	public function getNonConflictedVertices() {
		$nonConflictedVertices = array();
		foreach ($this->getVertices() as $vertex) {
			$nonConflicted = true;
			foreach ($this->getVertexNeighbours($vertex) as $neighbour) {
				if ($vertex->getId() != $neighbour->getId() && $vertex->getColor() == $neighbour->getColor()) {
					$nonConflicted = false;
				}
			}
			if ($nonConflicted == true) {
				if (!in_array($vertex, $nonConflictedVertices)) {
					$nonConflictedVertices[] = $vertex;
				}
			}
		}
		return $nonConflictedVertices;
	}
	
	protected function getNeighboursColors(Vertex $vertex) {
		$neighbours = $this->getVertexNeighbours($vertex);
		$colors = array();
		foreach ($neighbours as $neighbour) {
			if ($neighbour->getColor() != 0 && !in_array($neighbour->getColor(), $colors)) {
				$colors[] = $neighbour->getColor();
			}
		}
		return $colors;
	}
	
	public function getPossibleColors(Vertex $vertex) {
		$colors = $this->getNeighboursColors($vertex);
		$neighbours = $this->getVertexNeighbours($vertex);
		$minimalFree = $this->getMinimalFreeColor($neighbours);
		
		$colorsCount = count($colors);
		if ($colorsCount) {
			for ($i = 0; $i < $colorsCount; $i++) {
				$colors[] = $minimalFree;
			}
		} else {
			$colors[] = $minimalFree;
		}
		
		return $colors;
	}
	
	public function randomColoring($vertices = null) {
		if ($vertices === null) {
			$vertices = $this->getVertices();
		}

		foreach ($vertices as $vertex) {
			$possibleColours = $this->getPossibleColors($vertex);
			$color = $possibleColours[rand(0, count($possibleColours) - 1)];
			if ($color == 0) {
				throw new Exception("farba je 0!!");
			}
			$this->setVertexColor($vertex, $color);
		}
	}
	
	public function clearColors($vertices = null) {
		if ($vertices == null) {
			$vertices = $this->getVertices();
		}
		
		foreach ($vertices as $vertex) {
			$this->setVertexColor($vertice, 0);
		}
	}
	
		public function getBrelazColours() {
		return $this->brelazColours;
	}

	public function getFitness() {
		if ($this->check()) {
			$colors = $this->getBrelazColours() / $this->getColorsCount();
		} else {
			$colors = 1;
		}
		return $colors * (1 - ($this->getRealConflicts() / $this->getMaximumConflicts())) * (1 - (count($this->getConflictedVertices()) / count($this->vertices)));
	}
	
	public function getSerializedColors() {
		$vertices = array();
		foreach ($this->getVertices() as $vertex) {
			$vertices[$vertex->getId()] = $vertex->getColor();
		}
		return serialize($vertices);
	}
}

?>